package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.Arrays;

/**
 * (B卷,200分)- 竖直四子棋（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 竖直四子棋的棋盘是竖立起来的，双方轮流选择棋盘的一列下子，棋子因重力落到棋盘底部或者其他棋子之上，当一列的棋子放满时，无法再在这列上下子。
 * <p>
 * 一方的4个棋子横、竖或者斜方向连成一线时获胜。
 * <p>
 * 现给定一个棋盘和红蓝对弈双方的下子步骤，判断红方或蓝方是否在某一步获胜。
 * <p>
 * 下面以一个6×5的棋盘图示说明落子过程：
 * <p>
 * <p>
 * <p>
 * 下面给出横、竖和斜方向四子连线的图示：
 * <p>
 * <p>
 * <p>
 * 输入描述
 * <p>
 * 输入为2行，第一行指定棋盘的宽和高，为空格分隔的两个数字；
 * <p>
 * 第二行依次间隔指定红蓝双方的落子步骤，第1步为红方的落子，第2步为蓝方的落子，第3步为红方的落子，以此类推。
 * <p>
 * 步骤由空格分隔的一组数字表示，每个数字为落子的列的编号（最左边的列编号为1，往右递增）。用例保证数字均为32位有符号数。
 * <p>
 * 输出描述
 * <p>
 * 如果落子过程中红方获胜，输出 N,red ；
 * <p>
 * 如果落子过程中蓝方获胜，输出 N,blue ；
 * <p>
 * 如果出现非法的落子步骤，输出 N,error。
 * <p>
 * N为落子步骤的序号，从1开始。如果双方都没有获胜，输出 0,draw 。
 * <p>
 * 非法落子步骤有两种，一是列的编号超过棋盘范围，二是在一个已经落满子的列上落子。
 * <p>
 * N和单词red、blue、draw、error之间是英文逗号连接。
 * <p>
 * 用例
 * <p>
 * 输入	5 5
 * <p>
 * 1 1 2 2 3 3 4 4
 * <p>
 * 输出	7,red
 * <p>
 * 说明	在第7步，红方在第4列落下一子后，红方的四个子在第一行连成一线，故红方获胜，输出 7,red。
 * <p>
 * 输入	5 5
 * <p>
 * 0 1 2 2 3 3 4 4
 * <p>
 * 输出	1,error
 * <p>
 * 说明	第1步的列序号为0，超出有效列编号的范围，故输出 1,error。
 */
public class VerticalFourPieceChess {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = tmp[0];
        int n = tmp[0];

        int[] cols = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();*/

        int[] tmp = Arrays.stream("5 5".split(" ")).mapToInt(Integer::parseInt).toArray();
        int m = tmp[1];
        int n = tmp[0];

        int[] cols = Arrays.stream("1 1 2 2 3 3 4 4".split(" ")).mapToInt(Integer::parseInt).toArray();

        System.out.println(getResult(n, m, cols));
    }

    // 上，左，左上，左下
    static int[][] offsets = {{-1, 0}, {0, -1}, {-1, -1}, {-1, 1}};

    /**
     * @param n    宽 ，矩阵列数
     * @param m    高，矩阵行数
     * @param cols 落子的列的编号
     */
    public static String getResult(int n, int m, int[] cols) {
        int r = m;
        int c = n;

        // 构造棋盘，注意棋盘长宽都+1了，方便后面棋子获取
        int[][] matrix = new int[r + 1][c + 1];

        // 这里i对应第几步，由于题目是从第1步开始算，而这里 i 从0开始算，因此最终返回要i+1
        for (int i = 0; i < cols.length; i++) {
            // cols[i]代表第 i 步下在第几列
            if (cols[i] < 1 || cols[i] > c){
                return i + 1 + ",error";
            }

            // player落子颜色：1代表红色，2代表蓝色
            int player = i % 2 == 0 ? 1 : 2;

            // 落子逻辑
            int x = m;
            int y = cols[i];
            while (matrix[x][y] > 0) {
                x--; // 如果当前列底部有棋子，则需要往上查找
                if (x < 1){
                    return i + 1 + ",error"; // 如果当前列已经放满棋子，则报错
                }
            }
            matrix[x][y] = player; // 如果当前列底部没有棋子，则可以放入

            // i >= 6，即第七步及之后落子时，才可能产生四连击
            if (i >= 6 && isFour(x, y, player, matrix, r, c)) {
                return i + 1 + "," + (player == 1 ? "red" : "blue");
            }
        }

        // 双方都没有获胜
        return "0,draw";
    }

    public static boolean isFour(int x, int y, int player, int[][] matrix, int r, int c) {
        for (int[] offset : offsets) {
            int len = 1;

            // 向着某个方向延申判断是否存在相同子
            int x1 = x;
            int y1 = y;
            while (true) {
                x1 += offset[0];
                y1 += offset[1];

                if (x1 >= 1 && x1 <= r && y1 >= 1 && y1 <= c
                        && matrix[x1][y1] == player) {
                    len++;
                } else {
                    break;
                }
            }

            // 向着上面方向的反方向延申判断是否存在相同子（两个相反方向其实处于一条线上）
            int x2 = x;
            int y2 = y;
            while (true) {
                x2 -= offset[0];
                y2 -= offset[1];

                if (x2 >= 1 && x2 <= r && y2 >= 1 && y2 <= c
                        && matrix[x2][y2] == player) {
                    len++;
                } else {
                    break;
                }
            }

            // 如果此线可以形成四子连击，则直接返回true
            if (len >= 4) {
                return true;
            }
        }

        return false;
    }
}